package com.itheima.datastructure.heap;

import java.util.Arrays;

public class E04Leetcode295_1 {
    /*
    为了保证两边的数据量一致
    1.
    两边个数一样时，左边个数加一
    2.
    两边个数不一样的时候，，右边个数加一

    不能随便加入
    左边加一，新元素加在右边，左边加入右边弹出最下的
    右边加一，新元素加在左边，右边加入左边最大的
     */
    public void addNum(int num){
        if(left.getSize()==right.getSize()){
            right.offer(num);
            left.offer(right.poll());
        }else{
            left.offer(num);
            right.offer(left.poll());
        }
    }

    private Heap left=new Heap(10,true);//大顶堆
    private Heap right=new Heap(10,false);//小顶堆

    @Override
    public String toString() {
        //需要把大顶堆的元素倒序，小顶堆保持原样copy
        int size = left.size;
        int[] left = new int[size];
        for (int i = 0; i < left.length; i++) {
            left[size - 1 - i] = this.left.array[i];
        }

        int size1=right.size;
        int [] right=new int[size1];
        for(int i=0;i<right.length;i++){
            right[i]=this.right.array[i];
        }
        return Arrays.toString(left) + " <-> " + Arrays.toString(right);
    }

    //获取中位数
    public double fidMedian(){
        //两数一致取平均值
        if(left.getSize()==right.getSize()){
            return (left.peek()+ right.peek())/2.0;
            //不同，取大顶堆堆顶
        }else{
            return left.peek();
        }
    }




    public static void main(String[] args) {
        E04Leetcode295_1 test = new E04Leetcode295_1();
        test.addNum(1);
        test.addNum(2);
        test.addNum(3);
        test.addNum(7);
        test.addNum(8);
        test.addNum(9);
        System.out.println(test);
        System.out.println(test.fidMedian());
    }
}
